package lanqiao._02算法训练.page01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　娜娜是一个特别可爱的女孩子，作为学神的她最近在情感方面出现了一点点小问题。
 * 　　她暗恋的琦琦是一名学霸，他只喜欢长得漂亮和学习很好的女生。
 * 　　娜娜学习确实很神，但是她在琦琦面前却总是表现不出平时的神力。
 * 　　琦琦感受到了娜娜对他的爱，但是他还是觉得娜娜的学习并不是特别好，于是他出了一道题给娜娜。
 * 　　“娜娜，我们之间的关系需要在不断深入的同时保持一定的平衡，不可以你总是强势或者我总是弱势。”
 * 　　琦琦给了娜娜一些两两不等的数，希望娜娜能把这些数分成两组A和B，满足以下条件：
 * 　　1：每一次只能操作一个数，即只取出一个数分入A中或B中；
 * 　　2：每一次操作完成后，A中数之和与B中数之和的差不能超过r。
 * 　　新时代的丘比特们啊，帮帮娜娜吧！
 * 输入格式
 * 　　输入共两行。
 * 　　第一行包括两个正整数n和r，n表示琦琦一共给了n个数，r的意义见题目描述。
 * 　　第二行包括n个正整数，分别表示琦琦给的n个数。
 * 输出格式
 * 　　输出共两行，分别把A与B两组数按从小到大输出。
 * 　　注意输入中n个数的第一个必须分入A组。
 * 　　琦琦保证这样的输出唯一。
 * 样例输入
 * 4 10
 * 9 6 4 20
 * 样例输出
 * 4 6 9
 * 20
 * 样例说明
 * 　　先把4和6先后分入A组，再把20分入B组，最后把9分入A组。
 * 数据规模和约定
 * 　　很小，真的很小。
 * 思路：
 * dfs、全排列
 * 从小到达排序数组
 * vis数组标记每个数是否访问过
 * A组需要包含第一个数，用一个变量标记一下
 * 只有一个结果，使用一个变量找到一个结果结束dfs
 * @since 2022 - 10 - 30 - 13:58
 */
public class _09娜神平衡 {
}
class Main9{
    static int n, r;
    static int[] nums;
    //A组
    static List<Integer> A;
    //B组
    static List<Integer> B;
    //分别记录A组、B组中数的总和
    static int sum1, sum2;
    //找到一个情况就输出结束
    static boolean find;
    //要求A组必须包含第一个数
    static int num1;
    static boolean aContains;
    //全排列
    static boolean[] vis;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        //不可能的情况
        if(n <= 0 || r == 0) return;
        nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = sc.nextInt();
        }
        num1 = nums[0];
        aContains = false;
        //排序：从小的数开始选
        Arrays.sort(nums);
        //第一次将最小的数放在A里， A - 0  > r
        if(n == 1 && nums[0] > r) return;

        A = new ArrayList<>();
        B = new ArrayList<>();
        vis = new boolean[n];
        sum1 = 0;
        sum2 = 0;
        find = false;
        dfs(0);
    }
    static void dfs(int cnt){
        if(find) return;
        if(cnt >= n) { //所有数都分完了
            if(aContains){ //A组包含第一个数
                for(int i : A){
                    System.out.print(i + " ");
                }
                System.out.println();
                for(int i : B){
                    System.out.print(i + " ");
                }
                //结束dfs
                find = true;
            }
            return;
        }
        //全排列
        for(int i = 0; i < n; i++){
            if(!vis[i] && !find){
                if(Math.abs(sum1 + nums[i] - sum2) <= r){
                    A.add(nums[i]);
                    sum1 += nums[i];
                    vis[i] = true;
                    //当前数为第一个数
                    if(nums[i] == num1) aContains = true;
                    dfs(cnt + 1);
                    //回溯
                    A.remove(A.size() - 1);
                    sum1 -= nums[i];
                    vis[i] = false;
                    if(nums[i] == num1) aContains = false;
                }

                if(Math.abs(sum2 + nums[i] - sum1) <= r){
                    B.add(nums[i]);
                    sum2 += nums[i];
                    vis[i] = true;
                    dfs(cnt + 1);
                    //回溯
                    vis[i] = false;
                    B.remove(B.size() - 1);
                    sum2 -= nums[i];
                }
            }
        }
    }
}